class Solution {
public:
    vector<vector<int>> mamo;
    int uniquePaths(int m, int n) {
        mamo.resize(m+1);
        for (int i=1;i<=m;i++){
            mamo[i].resize(n+1,-1);
        }
        return dfs(m,n);
    }
    int dfs(int i,int j){
        if(i==0 || j==0){mamo[i][j]=0;return 0;}
        if (i==1 && j==1){mamo[i][j]=1;return 1;}
        if (mamo[i][j]!=-1)return mamo[i][j];
        mamo[i][j]=dfs(i,j-1)+dfs(i-1,j);
        return mamo[i][j];
    }
};
